Many computing applications manipulate identification strings that reference various entities such as data structures, external objects and processes. Such identification strings, which are hereinafter referred to as identifiers, tend to be large so that they can be distinguished from a great number of other identifiers. Identifiers also tend to be large in order for the schemes that organize them to be more flexible and more able to accommodate future additions of new identifers.
One common type of manipulation effected by such computing applications involves translating identifiers from a bulkier less manageable format to a smaller more manageable format that can be manipulated more easily. Such translations are performed to reduce the needless processing and memory demands that are made of a localized set of components, when the identifiers they are handling include fields that they do not need to access.
One example of a computing application that requires such translations arises in the field of telecommunications engineering, and more specifically in the operation of an Asynchronous Transfer Mode (ATM) switch. In an ATM network, the external connection identifier (ECI) of a cell, which can be processed by all nodes of the network, can comprise a Virtual Path Identifier (VPI), and a Virtual Channel Identifier (VCI). These identifiers, when considered in combination, can occupy binary words that are typically at least 28 bits long, and thus can assume billions of possible values. Usually however, it is not feasible or necessary for a switch to support such a large number of connections at one time primarily because of the vast amounts of context memory and processing resources required for each connection. As a result, a smaller number of connections is supported instead.
Accordingly, it is desirable to implement a system in ATM networks for translating a set of ECIs that can be manipulated by any of the switches into smaller more easily manageable internal connection identifiers (ICIs) that will only have to be manipulated by a single switch. At the same time, it is also desirable that the set of ECIs selected for translation comprise any subset of the full range of possible ECIs. That is, assuming the full range of ECIs comprises M ECIs, it is desirable that a switch capable of translating N ECIs into ICIs, be able to set each of its N ECIs to any one of the M possible ECIs.
Whether the target application is the above-described ATM network, or any other application wherein large bulky identifiers need to be converted into smaller, more manageable internal identifiers, present systems that translate identifiers have shortcomings.
Systems designed around direct one-stage look-up tables, wherein each table-entry is addressed by a large, external identifier and contains a smaller internal identifier, are economically impractical. This is because under such an approach, the size of the look-up tables must be set to equal the number of ECIs comprising the full range of external identifiers. For example, if an individual ATM switch can serve 100,000 connections, and the full range of ECIs extends from 0 to 1,000,000, the size of the look-up table would have to be 1,000,000 entries rather than 100,000 entries. Such large look-up tables are costly and wasteful.
Systems designed around constrained one-stage look-up tables cannot translate the full range of possible external identifiers, and thus are also undesirable.
Systems that use hashing functions to access look-up tables are complex, and may require expensive hardware to implement. Moreover, the time required to complete each translation may not be deterministic.
Systems designed around Content Addressable Memory (CAMs), wherein each entry is addressed by an internal identifier and contains an external identifier, are expensive. Furthermore, at present, a reasonably priced CAM does not have sufficient capacity to hold the number of internal identifiers required by many applications.
An improved system is thus desired for translating identifiers from a bulkier less manageable external format that can be manipulated by a broader range of components comprising a computing application, to a smaller more manageable internal format that can be more efficiently manipulated by a narrower range of those same components.
The desired system should also be able to translate any of the full range of external identifiers.
Another object of such a system is to achieve the translations using a simple and robust design that requires a minimal amount of memory and computation.
It is also desirable that the translation system exhibit fast and deterministic response-times.